COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a40.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Context-free Languages as Fixed Points\hfill}

Let $D↓A=\{\,x\mid A\aRa x, x\in T↑{\ast}\,\}$. If $y\in D↓A$, then there
is a derivation  
$A→X↓1X↓2\ldots X↓n\aRa y=y↓1y↓2\ldots y↓n$
with $X↓i\in\Sigma$, $X↓i\aRa y↓i$ by the partition theorem. So $y↓i\in D↓{X↓i}$,
$y\in D↓{X↓1}\otimes D↓{X↓2}\otimes\cdots\otimes D↓{X↓n}$, and
$D↓A\subseteq\bigcup↓{A→X↓1X↓2\ldots X↓n}
D↓{X↓1}\otimes D↓{X↓2}\otimes\cdots\otimes D↓{X↓n}$.
On the other hand, any element of $D↓{X↓1}\otimes\cdots\otimes D↓{X↓n}$ where
$A→X↓1\ldots X↓n$ is of the form $y↓1y↓2\ldots y↓n$ with $X↓i\aRa y↓i$, so
it belongs to~$D↓A$, and the inclusion runs both ways.
Thus, viewing the productions with~$A$ as lefthand side, say 
$A→BC\mid EF$, as a set equation $S↓A=S↓B\otimes S↓C\cup S↓E\otimes S↓F$,
one solution of the equation is $S↓A=D↓A$, $S↓B=D↓B$, etc.

On the other hand, we show that any simultaneous solution $S↓A$, $S↓B$, etc.,
of these set equations satisfies $D↓A\subseteq S↓A$, $D↓B\subseteq S↓B$,
etc., by induction on the length of derivation of $y\in D↓A$.

{\narrower\smallskip\rmn\noindent
{\bf Drill.} Prove it.
\smallskip}

\noindent
Then, viewing the productions as mapping the vector of sets 
$(S↓A,S↓B,S↓C,\ldots)$ 
into $(S'↓A,S'↓B,\ldots)$, where $S'↓A=S↓B\otimes S↓C\cup
S↓E\otimes S↓F$, etc., any fixed point of the mapping satisfies the set
equations, so $(D↓A,D↓B,\ldots)$ is a minimum fixed point of the mapping.



\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd
First draft (not published)
May 2, 1986.
%revised date;
%subsequently revised.

\bye